package com.easy.leetcode.dp;
//1049. 最后一块石头的重量 II
public class LastStoneWeightII {
    public int lastStoneWeightII(int[] stones) {
        int sum=0;
        for (int stone : stones) {
            sum+=stone;
        }
        int target=sum/2;
        //dp定义，容量为j的背包，能够装的最大价值
        int[] dp = new int[target+1];
        for (int i = 0; i < stones.length; i++) {
            for (int j = target; j >=stones[i] ; j--) {
                dp[j]=Math.max(dp[j],dp[j-stones[i]]+stones[i]);
            }
        }
        return sum-dp[target]*2;
    }
}
